from cal_time import cal_time
import random
import sys
#修改最大递归深度为10w
sys.setrecursionlimit(100000)
def partition(data, left, right):
    tmp = data[left]
    while left < right:
        # 从右边找比tmp小的数移动到左边
        while data[right] >= tmp and left < right:
            right -= 1
        # 把右边的值放在左边
        data[left] = data[right]
        # 从左边找比tmp大的数移动到右边
        while data[left] <= tmp and left < right:
            left += 1
        data[right] = data[left]
    data[left] = tmp
    return left

def _quick_sort(data,left,right):
    #至少两个元素
    if left<right:
        mid=partition(data,left,right)
        _quick_sort(data,left,mid-1)
        _quick_sort(data,mid+1,right)
    return data

@cal_time
def quick_sort(data):
    _quick_sort(data,0,len(data)-1)

li=list(range(10000))
random.shuffle(li)
print(_quick_sort(li,0,len(li)-1))
